//给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 
//
// 你需要返回给定数组中的重要翻转对的数量。 
//
// 示例 1: 
//
// 
//输入: [1,3,2,3,1]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: [2,4,3,5,1]
//输出: 3
// 
//
// 注意: 
//
// 
// 给定数组的长度不会超过50000。 
// 输入数组中的所有数字都在32位整数的表示范围内。 
// 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 
// 👍 292 👎 0


package service.week05.leetcode.editor.cn;

//Java：翻转对
public class P493ReversePairs {
    public static void main(String[] args) {
        Solution solution = new P493ReversePairs().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 归并排序
         *
         * @param nums
         * @return
         */
        int ans = 0;
        public int reversePairs(int[] nums) {
            mergeSort(nums, 0, nums.length - 1);
            return ans;
        }

        private void mergeSort(int[] arr, int l, int r) {
            if (l >= r) {
                return;
            }
            int mid = (l + r) >> 1;
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }

        private void calculate(int[] arr, int left, int mid, int right) {
            for (int i = left, j = mid; i <= mid; i++) {
                while (j < right && arr[i] > 2L * arr[j + 1]) {
                    j++;
                }
                ans += j - mid;
            }
        }

        private void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[right - left + 1];
            int i = left, j = mid + 1;
            //合并两个有序数组
            for (int k = 0; k < temp.length; k++) {
                if (j > right || (i <= mid && arr[i] < arr[j])) {
                    temp[k] = arr[i++];
                } else {
                    temp[k] = arr[j++];
                }
            }
            for (int k = 0; k < temp.length; k++) {
                arr[left + k] = temp[k];
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}